//Mike Ellie Rohan Fatma四个人参加自行车比赛，分别获得1-4名，它们每个人骑不同颜色的车（红，紫，蓝，绿）。
//基于以下线索，谁获得了第二名？

//Ellie骑紫色的车，Rohan没有骑绿色的车。
//010100, 10***0

//Mike和Ellie不是第一，也不是最后。
//$ME$ or $EM$

//骑蓝色车的人领先Fatma。
//**0010 < 11****

//骑绿色车的人领先了骑紫色车的人。
//**0001 < **0100

//用长度为4的整型数组记录四位选手及其信息，需要6位二进制位整数，前两位表示选手，后四位表示选手骑车的颜色，选手在数组中的下标代表选手排名
//具体表示如下：
//Color:Red(0001), Purple(0010), Blue(0100), Green(1000)
//Name:Mike(00), Ellie(01), Rohan(10), Fatma(11)

//使用回溯法递归循环遍历条件树，共有576种可能的结果。
//在所有可能的情况中，符合题目条件的情况共有4种，其中第二名均为Mike。
//具体算法如下所示：

#include <iostream>
#include <vector>

template <unsigned T>
void swap(int list[T], unsigned i, unsigned j);
void color_swap(int *i, int *j);
void reverse(int &data, int i);
int backtrack_find(int Name_list[4], int, int);
bool is_Green(int);
bool is_Blue(int);
bool is_Fatma(int);
bool is_Purple(int);
void print_in_bin(int);

std::vector<int> result;


int main(int argc, const char * argv[]) {
	

    int Name_list[4] {(0 | 1), ((1 << 4) | (1 << 1)),
      ((1 << 5) | (1 << 2)), ((1 << 4 | 1 << 5) | (1 << 3))};

    backtrack_find(Name_list, 0, 3);

    for(auto i: result)
	{
		switch (i & 48) {
		case 0:
				std::cout << "Mike" << std::endl;
				break;
		case 16:
				std::cout << "Ellie" << std::endl;
				break;
		case 32:
				std::cout << "Rohan" << std::endl;
				break;
		case 48:
				std::cout << "Fatma" << std::endl;
				break;
		default:
				std::cout << "Failed" << std::endl;
				break;
		}
	}
	
    return 0;
}


template <unsigned T>
void swap(int list[T], unsigned i, unsigned j)
{
    int temp_if = list[i] & 48;
    int temp_jf = list[j] & 48;
    int temp_ib = list[i] & 15;
    int temp_jb = list[j] & 15;
    
    list[i] = temp_jf | temp_ib;
    list[j] = temp_if | temp_jb;
}

void reverse(int &data, int i)
{
    int j = 1 << (i - 1);
    data = data ^ j;
}

void color_swap(int *i, int *j)
{
    int color_i = 15 & (*i);
    int color_j = 15 & (*j);
    *i = ((*i) & 48) | color_j;
    *j = ((*j) & 48) | color_i;
}

bool is_Green(int i)
{
    return (i & 8);
}
bool is_Blue(int i)
{
    return (i & 4);
}
bool is_Fatma(int i)
{
    return static_cast<bool>(i & 16) & static_cast<bool>(i & 32);
}
bool is_Purple(int i)
{
    return (i & 2);
}



int color_backtrack(int Name_list[4], int color_i, int color_j)
{
	if (color_i == color_j)
		return -1;
	for (int j = color_i; j <= color_j; ++j) {
		int Ellie = 0;
		int Rohan = 0;
		int Blue_Index = 0;
		int Fatma_Index = 0;
		int Green_Index = 0;
		int Purpel_Index = 0;
		
		for(int i = 0; i < 4 ; ++i)
		{
			if((Name_list[i] & 48) == 16)
			{
				Ellie = Name_list[i];
				break;
			}
		}
		for(int i = 0; i < 4 ; ++i)
		{
			if((Name_list[i] & 48) == 32)
			{
				Rohan = Name_list[i];
				break;
			}
		}
		for(unsigned i = 0; i < 4; ++i)
			if(is_Blue(Name_list[i]))
			{
				Blue_Index = i;
				break;
			}
		for(unsigned i = 0; i < 4; ++i)
			if(is_Fatma(Name_list[i]))
			{
				Fatma_Index = i;
				break;
			}
		for(unsigned i = 0; i < 4; ++i)
			if(is_Green(Name_list[i]))
			{
				Green_Index = i;
				break;
			}
		for(unsigned i = 0; i < 4; ++i)
			if(is_Purple(Name_list[i]))
			{
				Purpel_Index = i;
				break;
			}
		
		if((Ellie != 20) || is_Green(Rohan) || ((Name_list[0] & 48) == 0) || ((Name_list[0] & 48) == 16)|| ((Name_list[3] & 48) == 0) || ((Name_list[3] & 48) == 16) || (!(Blue_Index < Fatma_Index)) || (!(Green_Index < Purpel_Index)))
		{
			color_swap(&Name_list[j], &Name_list[color_i]);
			color_backtrack(Name_list, color_i + 1, color_j);
			color_swap(&Name_list[j], &Name_list[color_i]);
		}else
		{
			result.push_back(Name_list[1]);
		}
	}
	return -1;
}

int backtrack_find(int Name_list[4], int rank_i, int rank_j)
{
	if(rank_i == rank_j)
		return  -1;
	
	for(int j = rank_i; j <= rank_j; ++j)
	{
		color_backtrack(Name_list, 0,3);
		swap<4>(Name_list, j, rank_i);
		backtrack_find(Name_list, rank_i + 1, rank_j);
		swap<4>(Name_list, j, rank_i);
	}
	return -1;
}

void print_in_bin(int i)
{
    std::vector<int> stack;
    for(short j = 0; j < 6; ++j)
    {
        stack.insert(stack.begin(), ( i & 1 ));
        i = i >> 1;
    }
    for(auto i: stack)
        std::cout << i;
    
    std::cout << std::endl;
}
